COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "lsp.pub[1,clt]" source_file
C00014 ENDMK
C⊗;
.require "lsp.pub[1,clt]" source_file;
.turn off "{"
.at "z1" ⊂"%41%*"⊃
.at "zn" ⊂"%4n%*"⊃
.once center
%3A MICRO-MANUAL FOR LISP - MOSTLY TRUTHFUL%1

.once center
by John McCarthy


	LISP data are symbolic expressions that can be either
%2atoms%1 or %2lists%1.  %2Atoms%1 are strings of letters
and digits and other characters not otherwise used in LISP.
A ⊗list consists of a left parenthesis followed by
zero or more atoms or lists separated by spaces and ending with a right parenthesis.
Examples: $$A, ONION, (), (A), (A ONION A), (PLUS A (TIMES B ONION) 1)$.

	The LISP programming language is defined by rules for %2evaluating%1
certain LISP expressions to yield other LISP expressions as their values.
The function ⊗value used in giving these rules is not part of the LISP
language but rather part of the informal language in which LISP is being
defined.  Likewise, the italic letters ⊗e and ⊗a (sometimes with subscripts)
denote LISP expressions, the letter ⊗v (usually subscripted) denotes an
atom serving as a variable, and the letter ⊗f stands for a LISP expression
serving as a function name.
.item←0

#. ⊗⊗value $$(QUOTE$ e) = e⊗.  For example, the value of $$(QUOTE A)$ is $$A$.

#. ⊗⊗value $$(CAR$ e)⊗, where ⊗⊗value e⊗ is a non-empty list, is the first element
of ⊗⊗value_e⊗.  Thus ⊗⊗value_$$(CAR (QUOTE (A B C)))$ = $$A$.

#. ⊗⊗value $$(CDR$ e)⊗, where ⊗⊗value e⊗ is a non-empty list, is the
the list that remains when the first element
of ⊗⊗value_e⊗ is deleted.  Thus ⊗⊗value_$$(CDR (QUOTE (A B C)))$ = $$(B C)$.

#. ⊗⊗value $$(CONS$ e1 e2)⊗, is the list that results from prefixing
⊗⊗value_e1⊗ onto the list ⊗⊗value_e2⊗.  Thus
⊗⊗value $$(CONS (QUOTE A) (QUOTE (B C)))$ = $$(A B C)$.

#. ⊗⊗value $$(EQUAL$ e1 e2)⊗ is $$T$ if ⊗⊗value e1 = value e2⊗.  Otherwise,
its value is $$NIL$.  Thus value $$(EQUAL (CAR (QUOTE (A B))) (QUOTE A))$ = $$T$⊗.

#. ⊗⊗value $$(ATOM$ e) = $$T$⊗ if ⊗⊗value e⊗ is an atom; otherwise its
value is $$NIL$.

#. ⊗⊗value $$(COND$(pz1 ez1) ... (pzn ezn)) = value e%4i%*⊗,
where %2p%4i%1 is the the first of the %2p%1's whose value is not $$NIL$.
Thus
⊗⊗value $$(COND ((ATOM (QUOTE A)) (QUOTE B)) ((QUOTE T) (QUOTE C)))$ = $$B$⊗.

#. An atom ⊗v, regarded as a variable, may have a value.

#. ⊗⊗value $$((LAMBDA ($vz1 ... vzn) e) ez1 ... ezn)⊗ is
the same as ⊗⊗value_e⊗ but in an environment in which
the variables ⊗⊗vz1_..._vzn⊗ are take the values of the
expressions ⊗⊗ez1_..._ezn⊗ in the original environment.  Thus
⊗⊗value $$((LAMBDA (X Y) (CONS (CAR X) Y)) (QUOTE (A B)) (CDR (QUOTE (C D))))$
= $$(A D)$⊗.

#. Here's the hard one.  ⊗⊗value $$((LABEL$ f $$(LAMBDA ($vz1 ... vzn) e))
ez1 ... ezn)⊗ is the same as ⊗⊗value $$((LAMBDA ($vz1 ... vzn) e)
ez1 ... ezn)⊗, buT whenever ⊗⊗(f az1 ... azn)⊗ must be evaluated, ⊗f 
is replaced by ⊗⊗$$(LABEL$ f $$(LAMBDA ($vz1 ... vzn) e))⊗.
Lists beginning with $$LABEL$ define functions recursively.

	This is the core of LISP, and here are more examples:

⊗⊗value $$(CAR X)$ = $$(A B)$⊗ if ⊗⊗value $$X$ = $$((A B) C)$⊗, and
⊗⊗value $$((LABEL FF (LAMBDA (X) (COND ((ATOM X) X) ((QUOTE T) (FF (CAR X))))))
(QUOTE ((A B) C)))$ = $$A$.⊗
Thus $$((LABEL FF (LAMBDA (X) (COND ((ATOM X) X) ((QUOTE T) (FF (CAR X))))))$,
is the LISP name of a function ⊗ff such that ⊗⊗ff e⊗ is the
first atom in the written form of ⊗e. 
Note that the list ⊗ff is substituted for the atom $$FF$ twice.

Difficult mathematical type exercise: Find a list ⊗e such that ⊗⊗value e = e⊗.

	You may now program in LISP.  Call LISP system on a
time-sharing computer, type in a list, and LISP will type back its value.

%3Abbreviations%1

	The above LISP needs some abbreviations for practical use.
.item←0

#. So as not to describe a LISP function 
each time it is used, we define it permanently by typing
⊗⊗$$(DEFUN$ f (vz1 ... vzn) e)⊗.  Thereafter
⊗⊗(f ez1 ... ezn)⊗ is evaluated by evaluating ⊗e with the variables
⊗⊗vz1, ... ,vzn⊗ taking the values ⊗⊗value ez1, ... ,value ezn⊗
respectively.  Thus, after we define
$$(DEFUN FF (X) (COND ((ATOM X) X) ((QUOTE T) (FF (CAR X)))))$,
typing  $$(FF (QUOTE ((A B) C)))$, gets $$A$ from LISP.

#. The variables $$T$ and $$NIL$ are permanently assigned the values
$$T$ and $$NIL$, and $$NIL$ is the name of the null list ().  Therefore,
the above definition can be written
$$(DEFUN FF (X) (COND ((ATOM X) X) (T (FF (CAR X)))))$.

#. We have the permanent function definitions

$$(DEFUN NULL (X) (EQUAL X NIL))$ and

$$(DEFUN CADR (X) (CAR (CDR X)))$,

and similarly for arbitrary combinations of $$A$ and $$D$.

#. ⊗⊗$$(LIST$ ez1 ... ezn)⊗ is defined for each ⊗n to be
⊗⊗$$(CONS$ ez1 $$(CONS ... (CONS$ ezn $$NIL$)))⊗.

#. ⊗⊗$$(AND$ p q)⊗ abbreviates
⊗⊗$$(COND ($p q) ($$T NIL$))⊗.  $$AND$s with more terms are defined
similarly, and the propositional connectives
$$OR$ and $$NOT$ abbreviate similar conditional expressions.

	Now we can give some further examples of LISP function definitions:

$$(DEFUN ALT (X) (COND ((OR (NULL X) (NULL (CDR X))) X) (T (CONS (CAR X)
(ALT (CDDR X))))))$

defines a function that gives alternate elements of a list starting with
the first element.  Thus
$$(ALT (QUOTE (A B C D E)))$ = $$(A C E)$.

$$(DEFUN SUBST (X Y Z) (COND ((ATOM Z) (COND ((EQUAL Z Y) X) (T Z)))
(T (CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z))))))$

gives the result of substituting $$X$ for $$Y$ in $$Z$.  Thus

$$(SUBST (QUOTE (PLUS X Y)) (QUOTE V) (QUOTE (TIMES X V)))$ =
$$(TIMES X (PLUS X Y))$.